The present invention relates generally to the art of digital image processing. More particularly, the present invention relates to a novel and unobvious method and apparatus for error diffusion with reduced buffer requirements.
In the digital reproduction of documents, an image is conveniently represented as a bitmap, which may be described as an electronic image with discrete signals (hereinafter, pixels) defined by position and density. In such a system, density is described as one level in a number of possible states or levels. When more than two levels of density are used in the description of the image, the levels are often termed “gray”, indicating that they vary between a maximum and minimum, and without reference to their actual color. Most printing systems have the ability to reproduce an image with a small number of levels, most commonly two, although other numbers are possible. Common input devices including document scanners, digital cameras and the computer imagery generators, however, are capable of describing an image with a substantially larger number of gray levels, with 256 levels a commonly selected number, although larger and smaller levels are possible. It is required that an image initially described at a large set of levels also be describable at a smaller set of levels, in a manner which captures the intent of the user.
For color images, a plurality of bitmaps, each forming a color separation are combined. Each color separation may be defined by a number of gray levels in excess of the capability of the printer. In digital reproduction of color documents, each of the color separations is reduced from the input number of levels to a smaller output number of levels. The multiple color separations are combined together at printing to yield the final color print. Commonly, color documents are formed using cyan, magenta and yellow colorants or cyan, magenta, yellow and black colorants. A larger number or alternative colorants may also be used.
In printing documents, the desired density over an area is commonly achieved by halftoning, where image density variation is represented by placing greater or less numbers of ON pixels in a discrete area of the image for the binary case or by varying the number and/or the level of pixels for the non-binary case. In one halftoning method known as dithering or screening, over a given area having a number of gray separation pixels therein, a value representing the density of each separation pixel of an array of gray separation pixels within the area is compared to one of a set of preselected thresholds (the thresholds are stored as a dither matrix and the repetitive pattern generated by this matrix is considered a halftone cell) as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the dither matrix will be exceeded, i.e. the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the image pixels or cell elements for which the thresholds are exceeded might be printed as a maximum colorant value, while the remaining separation pixels are allowed to remain white, dependent on the actual physical quantity described by the data. The described halftoning method produces an output pattern that is periodic or quasi-periodic in the spatial coordinates.
Error diffusion is another halftoning method and is taught in “An Adaptive Algorithm for Spatial Greyscale” by Floyd and Steinberg, Proceedings of the SID 17/2, 75–77 (1976) (hereinafter, “Floyd and Steinberg”). Error diffusion attempts to maintain gray by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference or “error” between the gray level pixel value and the output value is propagated to a selected group or set of neighboring pixels, in accordance with a weighting scheme. The output binary pattern of the error diffusion algorithm and its derivatives is a pattern with a local periodicity related to the input density level, but with no global periodicity, see “Analytic Description of the 1-D Error Diffusion Technique for Halftoning,” Optics Communications, Vol. 52, No. 3, 165–168 (1984) by R. Eschbach and R. Hauck.
Other error diffusion methods include, “On the Error Diffusion Technique for Electronic Halftoning” by Billotet-Hoffmann and Bryngdahl, Proceedings of the SID, Vol. 24/3, (1983), pp. 253–258; and U.S. Pat. No. 5,226,094 to Eschbach. A technique related to error diffusion is taught in the MAE (Minimum Average Error) method of error diffusion described in “Images from Computers”, by M. Schroeder, IEEE Spectrum, March 1969, pp. 66–78, in which an error correction is performed that only affects a local neighborhood. One particularly effective error diffusion variant is taught in U.S. Pat. No. 5,353,127 to Shiau et al.
Error diffusion, in a variety of forms, has enjoyed widespread commercial success in connection with rendering digital images for a multitude of applications. The comparatively high rendering quality of error diffusion, when compared to standard halftoning, is somewhat compromised by slower rendering speeds and large buffer requirements for storage and processing of the error values. The large buffer requirements increase the manufacturing cost of a digital image processing apparatus implementing the error diffusion method.